#include <bits/stdc++.h>
using namespace std;

/*
2528. 最大化城市的最小电量
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

|x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。
一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。

这 k 座供电站可以建在多个城市。

 

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。
示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。
 

提示：

n == stations.length
1 <= n <= 105
0 <= stations[i] <= 105
0 <= r <= n - 1
0 <= k <= 109
*/

// 法一
class Solution {
public:
    using ll = long long;
    long long maxPower(vector<int>& stations, int r, int k) {
        // avg divide
        int n = stations.size();
        vector<ll> prev(n + 1, 0);
        // prev[i] = 前i个城市的电站总数，用于快速计算初始电量
        for (int i = 0; i < n; ++i) {
            prev[i + 1] = prev[i] + stations[i];
        }

        // init 电量
        vector<ll> init_power(n);
        for (int j = 0; j < n; j++) {
            int left = max(0, j - r);
            int right = min(n - 1, j + r);
            init_power[j] = prev[right + 1] - prev[left];
        }

        // edges
        ll left = 0, right = *max_element(init_power.begin(), init_power.end()) + k, ans = 0;

        // check 是否能让城市电量 >= mid
        auto is_possible = [&](ll mid) -> bool {
            vector<ll> add(n, 0); // 记录每个位置补充的电站数
            ll sum_add = 0;       // 当前城市获得的补充电量（滑动窗口维护）
            ll remain_k = k;      // 剩余可补充的电站数

            for (int j = 0; j < n; ++j) {
                // 移除超出当前城市供电范围的补充电站（滑动窗口左移）
                if (j > r) {
                    int out_pos = j - r - 1; // 不再影响j的补充位置
                    sum_add -= add[out_pos];
                }

                // 当前城市总电量 = 初始电量 + 补充电量
                ll curr_power = init_power[j] + sum_add;
                if (curr_power >= mid) continue; // 已满足，无需补充

                // 计算需要补充的电站数
                ll need = mid - curr_power;
                if (remain_k < need) return false; // 电站不足，不可行

                // 最优补充位置：j+r（覆盖最多后续城市，最大化利用）
                int best_pos = min(j + r, n - 1); // 避免超出城市范围
                add[best_pos] += need;
                sum_add += need;
                remain_k -= need;
            }
            return true;
        };

        while (left <= right) {
            ll mid = (right + left) / 2;
            if (is_possible(mid)) {
                ans = mid;
                left = mid + 1;
            } else right = mid - 1;
        }
        return ans;
    }
};

// 法二
using ll = long long;
class Solution {
public:
    vector<int> v; // 临时存储电站数组（避免修改输入）

    // 验证能否让所有城市电量≥mid：sum为初始滑动窗口电量，k为剩余可建电站数
    bool check(vector<int>& sta, int r, int k, ll mid, ll sum) {
        v = sta; // 拷贝原数组
        int n = sta.size();

        for (int i = 0; i < n; ++i) {
            // 滑动窗口右移：加入右侧新进入范围的电站（i+r位置）
            if (n - r > i) sum += v[i + r];
            // 滑动窗口右移：移除左侧退出范围的电站（i-1-r位置）
            if (r < i) sum -= v[i - 1 - r];

            if (mid > sum) { // 当前电量不足，需补充
                ll dif = mid - sum; // 需补充的电站数
                if (k < dif) return 0; // 电站不足，不满足
                k -= dif;
                // 最优补充位置：i+r（覆盖最多后续城市），避免越界
                if (n > i + r) v[i + r] += dif;
                sum = mid; // 补充后电量达标，直接更新sum
            }
        }
        return 1; // 所有城市均满足≥mid
    }

    long long maxPower(vector<int>& stations, int r, int k) {
        // 初始sum：第一个城市的供电总和（范围0~r-1）
        ll sum = reduce(begin(stations), begin(stations) + r, 0LL);
        // 二分边界：left=最小可能电量，right=总电站数+额外k座（最大可能电量）
        ll left = 0LL, right = reduce(begin(stations), end(stations), 0LL) + k;

        // 二分查找最大可行mid
        for (; left <= right;) {
            ll mid = ((right - left) >> 1) + left; // 避免溢出
            if (check(stations, r, k, mid, sum)) left = mid + 1; // 可达成，尝试更大
            else right = mid - 1; // 不可达成，尝试更小
        }
        return right; // 最终最大可行的最小电量
    }
};